package LeedCode_BinaryTree;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:寻找二叉树的最近公共祖先结点
 * User: 阿宾
 * Date: 2024-11-26
 * Time: 20:14
 */
public class Demo8 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }
    //方法1
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);//判断左子树
        TreeNode right = lowestCommonAncestor(root.right,p,q);//判断右子树
        if(left != null && right !=null){
            return root;
        }
        return left != null ? left : right;

    }
    //方法2
    //利用栈来实现，通过找到根节点到P q的路径，然后将路径分别保存在两个栈中，然后进行出栈，首个相同的元素就是公共祖先

    /**
     * 判断root到target是否存在路径，如果存在将其存储在栈中
     * @param root
     * @param target
     * @param stack
     * @return
     */
    private boolean findPath(TreeNode root, TreeNode target, Stack<TreeNode> stack){
        if(root == null){
            return false;
        }
        //将当前节点加入栈中
        stack.push(root);

        //找到目标节点
        if(root == target){
            return true;
        }
        //递归左右子树
        if(findPath(root.left,target,stack) ||findPath(root.right,target,stack)){
            return true;
        }
        //当前节点不再路径中，要弹出栈
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        //使用栈保存路径
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        //找根到节点p q的路径
        findPath(root,p,stackP);
        findPath(root,q,stackQ);

        // 调整两个栈的大小，使得它们的元素数量相同
        while (stackP.size() > stackQ.size()) {
            stackP.pop();
        }
        while (stackQ.size() > stackP.size()) {
            stackQ.pop();
        }
        //此时两个栈元素数量相同，开始比较
        while (!stackP.empty() && !stackQ.empty()){
            //找到第一个相同的元素，然后弹栈返回
            if(stackP.peek() == stackQ.peek()){
                return stackP.pop();
            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }
    public static void main(String[] args) {

    }
}
